#include <iostream>
#include <string>
using namespace std;
int dp[1005][1005] = {};

int minDistance(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    for (int i = 0; i <= n; i++) dp[0][i] = i;
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] =
                    1 + min(dp[i][j - 1], min(dp[i - 1][j], dp[i - 1][j - 1]));
        }
    }
    return dp[m][n];
}

// 编辑距离